package leetcode.editor.cn;

//累加数是一个字符串，组成它的数字可以形成累加序列。 
//
// 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。 
//
// 给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。 
//
// 说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。 
//
// 示例 1: 
//
// 输入: "112358"
//输出: true 
//解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
// 
//
// 示例 2: 
//
// 输入: "199100199"
//输出: true 
//解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199 
//
// 进阶: 
//你如何处理一个溢出的过大的整数输入? 
// Related Topics 字符串 回溯 👍 193 👎 0

//Java：累加数
public class AdditiveNumber_306 {
    public static void main(String[] args) {
        Solution solution = new AdditiveNumber_306().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isAdditiveNumber(String num) {
            return dfs(num, num.length(), 0, 0, 0, 0);
        }

        /**
         *
         * @param num 原字符串
         * @param length 字符串长度
         * @param index 当前开始获取数字的下标
         * @param sum 前面已求得得和
         * @param pre 前面一个数
         * @param count 当前已获取得数字个数
         * @return 能否得到一个数使其等于sum
         */
        public boolean dfs(String num, int length, int index, long sum, long pre, int count) {
            if(index == length) return count>2;
            for (int i = index; i < length; i++) { // 遍历index后面的数
                long cur = subNum(num, index, i);
                if (cur < 0) continue;
                if (count >= 2 && cur != sum)  continue;// 前面有两个数，但当前遍历到的不是他们的和
                if(dfs(num, length, i + 1, cur + pre, cur, count + 1)) return true;
            }
            return false;
        }

        /**
         * 获取[left,right]组成的数字
         */
        public long subNum(String num, int left, int right) {
            if (left < right && num.charAt(left) == '0')
                return -1;
            long res = 0;
            for (int i = left; i <= right; i++) {
                res = res * 10 + num.charAt(i) - '0';
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
/**
 * 199100199
 * index  sum  pre  count   cur
 * 0      0    0    0       1(i=0)
 * 1      1    1    1       9(i=1)
 * 2      10   9    2       9(i=2) -> 91(i=3) -> ... X
 * 1      1    1    1       9(i=1) -> 99(i=2)
 * 3      100  99   2       1(i=3) -> 10(i=4) -> 100(i=5)
 * 6      199  100  3       1(i=6) -> 19(i=7) -> 199(i=8)
 * 9      299  199  4       index == len
 */
}
